全网热议的RMM第三题，到底怎么解？

原文|罗教授  翻译|Helen  审校|Jining

文 5501字  阅读时间视个人情况而定

导语：

又干又硬的货来了！本文是罗教授对2019年RMM第三题的独家解析，建议有一定数学基础的朋友阅读，也欢迎对这道题目感兴趣、有见解的朋友与我们进行讨论！

题目：Given any positive real number ε, prove that, for all but finitely many positive integers v, any graph on v vertices with at least(1 + ε)v edges has two distinct simple cycles of equal lengths.

给定任意正实数ε，请证明，除了有限个反例之外，所有正整数v都满足：所有由v个顶点和至少(1 +ε)v 条边构成的图，都存在一对等长的不同简单圈（注意，简单圈不允许重复出现相同的顶点）。

在开始证明之前，我们先来介绍几个图论中基本的概念：

顶点（vertex）：图论中图（graph）的基本组成部分是顶点（vertex）和连接顶点的边（edge）

边（edge）：连接两个顶点的线叫边（edge）

相邻（adjacent）：如果两个顶点之间存在一条边，我们说它们是相邻的

度数（degree）：对于任何一个顶点v，与它相临的所有顶点的总数叫做这个顶点的度数, 用deg(v)表示

邻域（neighborhood）：对于任何一个顶点v，与它相临的所有顶点组成的集合叫做v的邻域，用N(v)表示

路径（path）：图论中，路径的本质是一个顶点序列，它的每个顶点有一条边连接该序列中下一顶点。一条路径可能是无穷的，但有限路径有一个最先顶点，称为起点，和最后顶点，称为末点，这两个顶点都叫做端点

圈（cycle）：图论中，圈从一个顶点起步，沿着不重复的边，不重复的顶点为途径，回到起点的闭合路径

连通性（connectedness）：如果对于图中的任何两个顶点，我们都能找到一条路径以它们为两个端点，那我们说这个图是联通的

树（tree）：如果图符合以下标准：①边的数量是顶点数量减一 ②图是联通的 ③图中不存在圈，我们说这幅图是树

环（loop）：一条连接顶点本身的边，在这道题中是不允许出现的

围长（girth）：图中最短圈包含的边数，比如一个正方形的围长就是4。不存在圈的图，它的围长是无穷大的

看到这道题，如果真的花时间思考，我们第一感觉，应该是试图找到顶点和边的关系。我们知道一个连通图，假设它有V个顶点，如果我们只有V-1条边，是不可能出现圈（回路）的，否则这幅图就不是联通图了。

但是，当我们有V条边的时候，就一定会出现一个圈（回路）。实际上，在此基础上我们每加一条边，就会创造出一个新的圈。假设我们有V+1条边的时候，图中只有一个圈，那么当我们从这个圈里去掉一条边，这个图中就不再有圈了，但是图中仍然有V个顶点，就必须要存在一个圈。所以我们的假设并不成立，图中至少有两个圈

在这里我们介绍一个新的定义，叫做余量，就是我们描述的边的数量E减去（V-1）, 等于E-V+1，用来描述一幅图里边多余顶点的量。直觉上，我们知道这个量大致决定了我们图中圈的数量。

再进一步想，其实当图中的边越来越多，圈就会越来越多，并且这些圈会互相交叉，圈的周长也会越来越小。这道题目就是要把这种直觉具体化，让我们证明当余量与图中顶点数保持线性增长关系的时候（即V= (1 + ε)N ），在N足够大的情况下，图中一定会出现周长相同的简单圈。

再回到题目，题目也非常新颖，用到了“有限个反例”这样的短语，带有浓重的数学科研色彩。如果我们想要正面解决这道题，唯一的办法似乎是在任意的一幅图里构造性地找到这样两个圈，但是题目又告诉我们，这个情况存在有有限个反例，几乎是在告诉我们此路不通了。正着走走不通，不如想想怎么迂回前进。那我们不妨换个角度：证明以下引理，通过这一引理来引出矛盾，实现反证。

引理1：对于任意正实数ε，自然数N，证明对于命题拥有N个顶点，(1 + ε)N 条边的图存在长度小于εN的圈， 只存在有限个反例。

假设一幅图有N个顶点，有至少(1 + ε)N条边，且图中所有圈的长度都不一样，我们需要在N足够大的时候构造矛盾来证明这一假设不成立。那想象我们进行这样一种操作：我们找到图中最短的圈，从这个圈中移走一条边，那么这个圈就被我们破坏掉了。所以在新的图中，最短圈的长度比原来大，也就是围长在这个过程中严格地增长。

那么如果我们重复这个过程εN/2次，剩下的图至少还有(1 + ε)N - εN/2 = (1 +ε /2)N条边。但是这个时候，因为我们重复了这个过程 εN/2次，剩下的图中要是还有圈，它的长度一定大于εN /2。但是根据引理1，剩下的图中有(1+ε/2)N条边，则它一定有长度小于εN / 2的圈，出现矛盾。所以，并不可能在(1 + ε)N条边的图中所有简单圈长度各不相同，命题得证。

于是剩下的部分我们就只需要证明上面的引理成立。

为了证明引理1，首先我们考虑这样一个函数F， 定义如下：

F(N,g) 表示顶点数为N，围长最小为g的图余量的最大值。即，一个有N个顶点的图中，想要保证围长不小于g，那么这个图中最多可以有F(N,g) + N - 1条边。不难发现，想要证明上面的引理，我们需要研究的是F(N, εN)的性质。

如果F(N, εN)是一个关于其第一个自变量的的“亚线性函数”（即增长速率低于线性函数的函数，比如对数函数、平方根函数），那么我们就知道，为了保证一个有N个顶点的图的围长不小于εN，则这个图的余量只能是一个N的亚线性函数，那么一个有N个顶点,  (1 + ε)N条边的图的围长在N足够大的时候自然一定小于εN，引理1因此得证。

亚线性函数（sublinear）示意图

所以为了证明引理1，我们只需要证明下面的引理2。

引理2：给定ε和N，g(x) = F(x, εN)是关于x的亚线性函数。即，g的增长速度低于线性函数，给定εN，一定存在一个x₀，使得对于x>x₀，一定有g(x) < εx。

接下来我们讨论如何证明引理2。这个函数g的性质其实不好直接讨论，但我们发现一个图和它经过简单删减之后得到的简化图的函数g之间有一些相关性，因此我们可以确立简单的初始值，然后通过讨论这些递推关系来确定g的增长速率。

首先我们设在这样的图中是不可能发现孤立的点的。一旦出现孤立点m（即度数为0的顶点），那么选取除了m以外的任一顶点n，并在G里添加nm这条边，顶点数和围长都和G相同（nm不可能是任何圈的一部分，因为任何圈里的每个顶点度数为2，而此时m的度数为1），而边数大于G，所以G并不是满足F定义中余量最多的图，这样的G不会决定F的函数值，无须考虑。所以我们只需要讨论每个顶点度数至少为1的那些图G，我们把这些图分为以下两种状况：

第一种情况：

G中有一片叶u（度数为1的顶点），删除u和它对应的那条边，那么新的图G’中其实少了一个顶点和一条边。那么根据余量的定义（E-V+1, E和V同时减小了1），我们知道G’的余量等于F(N, εN)，也就是G的余量。既然删除这个顶点并没有改变图的围长，我们知道G’ 是个拥有N个顶点，围长εN的图。那么这样图的余量应该小于等于同类图的最大值，也就是说F(N, εN) ≤ F(N−1,εN)，也即在这种情况下g(N) ≤ g(N - 1)。实际上是严格等于的，这里不再赘述，留给小伙伴们考虑。

第二种情况：

图中所有顶点的度数至少为2。现在我们假设G中没有长度小于εN的圈。那么选取图中任意一个顶点u, 它的度数至少是2，然后选取距离u小于等于(εN/2)−1顶点和它们之间的边，形成新的图H。我们认定H是树。假设H不是树，那么必然存在一个圈，假设y，z在圈中是相邻的，那么我们一定可以从y走到u再走回y，这中间的步数小于等于((εN/2)−1) + ((εN/2)−1) + 1 ，这个量是严格小于εN的。但是因为图中并不存在长度小于εN的圈，所以这样的圈并不存在，H一定是树。

话又说回来，这棵树也是非常奇怪的树。首先既然H是G的一部分，它不能有多于N个顶点。同时对于树的根u，它的深度是εN/2，这个深度是N的线性函数，而树中的顶点数又常常是随着树的深度指数增长的，这就对这棵树构成了很严苛的限制。（在接下来的计算中，我们会丢掉一些常数，后面我们会看到，在不同函数增长速率的比较中，这些常数项无伤大雅）

想象一下这颗奇怪的树H，首先所有的顶点度数都至少是2，也就是说这是一颗没有叶的树。而度数为三或更高的顶点会连锁反应，产生越来越多的顶点。但是我们的顶点数量又十分有限，也就是说，从u出发，我们应该能找到一条长度可观的路径，除去两端点，其中顶点的度数都为2。而这条路径，在之后的证明中也扮演了重要的角色。

这条路径的官方定义叫做孤立路径，它是除了两个端点之外，每个中间顶点的度数都是2的路径。因为每个中间顶点都要连接路径中与之相邻的两个点，所以它们不和该路径之外的任何顶点相邻。

我们设G中最长的孤立路径长度为m，那么对于t = 0，1，2，3…, (εN/2) − 1, 我们说St是距离u有t步的所有顶点的集合。既然图中所有点的度数都至少是2，那么对于St中任意一个顶点，它至少连接一个St+1中的顶点。

这个过程很像细菌的分裂生殖，在每一个时刻，细菌要么发生分裂，要么仅仅维持原数量、不发生分裂。不分裂的状态每次最多只能持续M次(左右)，并且一共会有(εN/2)−1个时间点，于是即使在分裂次数最少的状态下，也最少会发生大概(εN/2M)次分裂，最后剩下大概2^(εN/2M)个细菌。

回到我们的树中，这意味着这棵树里应该有至少2^((εN)/(2M))个顶点。但是我们知道这棵树最多只有N个顶点（因为它只是G的一个子图），也就是说 N≥ 2^( (εN)/(2M) ) 定义lg()为2底数的对数，那么我们知道：lg(N) ≥ (εN)/(2M)。也就是说，M ≥ (εN)/(2lg(N))。

换句话讲，为了保证这棵树中的顶点数不会超过整个图里的顶点数，G里必须至少有一条长度大于等于(εN)/(2 lg(N))的孤立路径。

现在，删去G中这条最长的孤立路径，和它上面的M+1个顶点来获得图G’。那么新的图围长也仍然大于等于εN。因为边越少，圈就应该越大，只有加上一些边才有可能产生更小的圈，就像我们考虑第一种情况的时候一样。

另外我们知道G’是一幅有N-M-1个顶点，N-M条边，围长至少为εN的图，那么G’的余量小于等于F(N-M, εN) - 1,  因为F(N-M,εN) 表示这类图余量的最大值。同时，因为我们删掉了M条边，和连接它们的M+1个顶点，G’的余量应该刚好等于F(N, εN)-1。

翻译成数学语言就是：

F(N, εN) − 1 ≤ F(N−M,εN)

也就是说：

F(N, εN) ≤ F(N−M,εN) + 1

其中M ≥ (εN)/(2lg(N))

亦即g(N) ≤ g(N - M)+ 1, M ≥ (εN)/(2 lg(N))

现在我们回过头去证明为什么对于足够大的N，我们一定能得到F(N, εN)小于等于εN。

回想第一种情况我们得到的结论：F(N, εN) ≤ F(N−1,εN)。

观察两种情况我们的到的结论。注意到我们的围长始终保持在εN。但是顶点数却在减少。对于这两种情况，通过递归（recursion）的思想，我们可以分别利用一二两种情况的不等式，把函数F化简，退化到一个容易思考的情况和取值。

我们知道这里的N表示顶点，第二个变量表示图中最小圈的长度。如果我们利用这两个不等式，让N持续减小，那么最终N会小于第二个变量，也就是说图的顶点数小于图中最小圈的长度，我们知道这种情况是不可能的。所以此时F(N,g)的值必须为0，即x< εN时，g(x) = 0，这就是函数g的初始值。

实际上，当我们尝试递归地考虑F(N, εN)的取值的时候，有时候会遇到第二种情况，也就是回到F(N−M, εN) + 1，另外的时候会遇到第一种情况。所以并不是每次都会碰上“+1”。而最终都会回归到一个N'值使F(N’, εN)=0，g(N') = 0，也就是我们前面描述的情况。每一次我们基本上会将第一个变量减小至少(εN)/(2 lg(N))。

而这个下界在之后的操作中也仍然成立，因为顶点数量减少到合适的N’后，围长仍然保持在εN，M始终满足M ≥ (εN)/(2 lg(N’))，甚至还要大于等于(εN)/(2 lg(N))。所以说，大约(2 lg(N))/ε步之内，第一个变量一定会变成0，也就是说，(2 lg(N))/ε步之内，F(N,εN)一定会小于等于εN，因为每一步贡献了一个“+1”，所以F(N,εN) ≤ (2 lg(N))/ε，甚至比我们预期的F(N, εN) ≤ εN还要严格。

通过以上的分析，我们可以用函数的语言来描述g(x)：它是一个比较奇怪的分段函数，首先它的初始值是0，而对之后的取值它有两种情况，有时候g(x) = g(x-1)，另外的时候g(x) = g(x-m)+1， 其中m≥ (εx)/(2 lg(x))。通过观察，我们知道这个函数的增长速率是严格小于线性函数（f(x) = x）的，也就是说，思考f(x) = εx (ε>0) 这样的线性函数，当x足够大的时候，f(x) 一定大于 g(x)。

至此，我们也完成了引理2的证明。

最后，如果我们在计算中更加精细严密，就可以得到更强的结论，它甚至能让我们证明存在趋向于sqrt(Nlog(N))这个数量级的函数f(N)，使得每个有N个顶点，N + f(N)条边的简单图拥有两个同样长度的不同的圈。

如果对罗教授的英文原文感兴趣，可以点击下方“阅读原文”查看我们之前的推送。

喜欢这篇文章吗？欢迎给我们留言，探讨有趣的数学问题，如果你还想看其他的相关内容，也可以向我们提出来哦！ 

相关推荐